package question.solution22;

import question.SolutionTemplate;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution22 implements SolutionTemplate {

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if(n==0)return result;
        getSubString(n, 0, 0, new StringBuilder(), result);
        return result;
    }

    private void getSubString(int bracketCount, int leftBracketCount, int rightBracketCount, StringBuilder parentString, List<String> result){

        if(leftBracketCount + rightBracketCount == 2*bracketCount){
            result.add(parentString.toString());
            return;
        }
        if(leftBracketCount == rightBracketCount){
            leftBracketCount++;
            parentString.append('(');
            getSubString(bracketCount, leftBracketCount, rightBracketCount, parentString, result);
            leftBracketCount--;
            parentString.deleteCharAt(parentString.length()-1);
        }else if(leftBracketCount > rightBracketCount && leftBracketCount < bracketCount){
            leftBracketCount++;
            parentString.append('(');
            getSubString(bracketCount, leftBracketCount, rightBracketCount, parentString, result);

            leftBracketCount--;
            rightBracketCount++;
            parentString.deleteCharAt(parentString.length()-1);
            parentString.append(')');
            getSubString(bracketCount, leftBracketCount, rightBracketCount, parentString, result);
            rightBracketCount--;
            parentString.deleteCharAt(parentString.length()-1);
        }else if(leftBracketCount > rightBracketCount){
            rightBracketCount++;
            parentString.append(')');
            getSubString(bracketCount, leftBracketCount, rightBracketCount, parentString, result);
            rightBracketCount--;
            parentString.deleteCharAt(parentString.length()-1);
        }
    }

    @Override
    public void test() {
        System.out.println(generateParenthesis(3));
    }

}
